1. Field of the Invention
The present invention relates to a method and apparatus for generating a high-quality pattern in accordance with an edge for defining a pattern such as a character pattern.
2. Description of the Related Art
In general, an edge is drawn and then the inside of an area surrounded by an edge line or edge lines is filled to generate a pattern. The following first to third methods are available to perform filling of an area defined by the edge line or lines.
According to the first method, a point designated within a defined area is continuously shifted to determine whether the shifted point is located inside or outside the defined area. When a given point is determined to be present inside the area, this point is subjected to filling processing. This method is used in graphic processing in a personal computer or the like. The determination operation is performed in units of points, and its processing speed is low. In addition, this method is based on "continuity of the area", back tracking must be generally performed at a branch point during filling.
According to the second method, a bit map memory which stores edge line data is scanned in a predetermined direction (filling direction) to perform filling of points as "1" from, e.g., an odd-numbered "1" point to an even-numbered "1" point (i.e., even-odd filling). The second method does not require back tracking. In the even-odd filling scheme, the number of crossings between a scanning line and an edge line is counted. When a count represents an odd number, the corresponding point is determined to be present inside the edge line. Otherwise, the point is determined to be present outside the edge line. According to the second method, however, when the number of dots of, e.g., a sharp end of a character pattern in the filling direction is one (this sharp end is defined as a one-dot sharp end), a subsequent dot string from the sharp-end dot is also filled, resulting in inconvenience. In order to overcome this drawback, character pattern design must be performed not to generate a one-dot sharp end (a sharp dot having only one dot in a direction perpendicular to the filling direction is not called a one-dot sharp end), resulting in cumbersome, time-consuming operations. In order to generate a one-dot sharp end, an edge line of a character pattern having a one-dot sharp end must be overwritten after a character pattern having no one-dot sharp end is generated by filling processing.
According to the second method, when edge lines of a character pattern do not overlap each other, as shown in FIG. 1A, a correct character pattern shown in FIG. 1B can be obtained. However, when edge lines of a character pattern overlap on the same lattice line and form a one-dot line width due to pattern reduction or the like, as shown in FIG. 1C, a wrong character pattern shown in FIG. 1D is undesirably generated. The filling direction in FIGS. 1B and 1D is a y direction (i.e., downward direction in FIGS. 1B and 1D).
The third method is a filling method in accordance with a non-zero winding number scheme used in the Post Script as a page descriptive language developed by Adobe Systems Inc. As shown in FIG. 2A, when a drawing direction of an edge line is directed to the left with respect to a vector from the infinity, i.e., a vector RV representing a filling direction, a winding number WN is incremented by one. However, when the drawing direction of an edge line is directed toward the right, as shown in FIG. 2B, the winding number is decremented by one. If the resultant winding number is zero, the corresponding crossing is determined to be present outside the edge line. Otherwise, it is determined to be present inside the edge line. According to the third method, segments constituting an edge line of a character must be sorted and listed in accordance with a given standard such as y-coordinates. When a "FILL" command is to be executed, a program loop is generated to scan scanning lines, e.g., lines parallel to the x-axis, downward. All intersections between the scanning lines parallel to the x-axis and the segments in the list must be obtained every loop. The descriptive contents of the segments are checked in an order of x-coordinates of the intersections to determine the drawing directions (upward or downward direction) of the lines, and the winding numbers (to be referred to as WNs hereinafter) are obtained. A line for a non-zero interval of the WNs is drawn in the bit map memory. The above operations are repeated in the program loop according to the third method.
10 As described above, according to the third method, the list of segments constituting the edge must be checked every line. For this reason, a long processing time is required for a complicated pattern such as a kanji (Chinese character) pattern whose segment list is relatively long. The computation of the above intersections must also be repeated by the "total number of dots of the edge line". As described above, in filling processing based on the conventional even-odd scheme, a line having a one-dot width and a character pattern having a one-dot sharp end cannot be accurately generated. High-speed processing cannot be performed in filling processing based on the non-zero winding number scheme. In either scheme, filling processing is performed in units of dots, and the processing speed is inevitably low.